package leetcode5;

import java.util.Arrays;

/*
* 41. 缺失的第一个正数*/
public class test15 {
    /*
    * 自己算法残缺*/
//    public int firstMissingPositive(int[] nums) {
//        Arrays.sort(nums);
//        if (nums[0] > 1)
//            return 1;
//        if (nums[nums.length - 1] < 1)
//            return 1;
//        for (int i = 0; i < nums.length - 1; i++) {
//            if (nums[i] >= 0) {
//                if (nums[i] != nums[i + 1] - 1 && (nums[i] + 1) > 0) {
//                    return nums[i] + 1;
//                }
//            }
//        }
//        return nums[nums.length - 1] + 1;
//    }
    public int firstMissingPositive(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                // 交换 nums[i] 和 nums[nums[i] - 1]
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return nums.length + 1;
    }

}
